import collections
from typing import List


class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:
        count = collections.Counter(flowers)

        # 计算非零前缀和
        # 计算以每一个数为第一朵花的砍花得分
        cache = {}
        prefix = [0]
        for i in range(len(flowers)):
            if flowers[i] not in cache:
                cache[flowers[i]] = prefix[-1]
            if flowers[i] > 0:
                prefix.append(prefix[-1] + flowers[i])
            else:
                prefix.append(prefix[-1])

        # 从后向前遍历选择最优解
        ans = float("-inf")
        visited = set()
        for i in range(len(flowers) - 1, -1, -1):
            if count[flowers[i]] > 1:
                if flowers[i] not in visited:
                    ans = max(ans, prefix[i + 1] - cache[flowers[i]] + (flowers[i] * 2 if flowers[i] < 0 else 0))

        return ans


if __name__ == "__main__":
    print(Solution().maximumBeauty(flowers=[1, 2, 3, 1, 2]))  # 8
    print(Solution().maximumBeauty(flowers=[100, 1, 1, -3, 1]))  # 3
    print(Solution().maximumBeauty(flowers=[-1, -2, 0, -1]))  # -2

    # 测试用例173/207
    print(Solution().maximumBeauty(flowers=[-5, -1, 2, -1]))  # 0

    # 测试用例199/207
    print(Solution().maximumBeauty(flowers=[-5, -5, -8, -10, 5]))  # -10
